# !/usr/bin/env python
# -*-coding:utf-8 -*-
"""
@Author : Ayao
@Time   : 2022/5/23
@File   : x 的平方根.py
"""


# https://leetcode.cn/leetbook/read/binary-search/xe9cog/

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 1: return x
        left, right = 1, x
        while left <= right:
            mid = left + (right - left) // 2
            if mid <= x / mid and x / (mid + 1) < (mid + 1):
                return mid
            elif mid < x / mid:
                left = mid + 1
            else:
                right = mid - 1


for i in range(40):
    res = Solution().mySqrt(i)
    print(i, res)
